package Algorithms;

import java.util.ArrayList;

import General.AdjacencyMatrix;

public class RandomCentersSelection extends CentersSelectionAlgorithm {

	public RandomCentersSelection(AdjacencyMatrix a) {
		super(a);
	
	}


	public int[] run() 
	{
		int size=(int)Math.ceil(n/4.0);
		int[] centers = new int[size];
		ArrayList<Integer> list = new ArrayList<Integer>(n); // for first stage
		ArrayList<Integer> list2 = new ArrayList<Integer>(n); // for second stage
		for (int i=0; i<n; i++)
		{
			list2.add(i);
			list.add(i);
		}
		int r= (int)(Math.random()*n);
		centers[0]=r;
		byte[] vec=a.getVector(r);
		list2.remove(new Integer(r));
		for (int i=0; i<n; i++)
			if (vec[i]==1)
				list.remove(new Integer(i));
		int i=1;
		while (!list.isEmpty() && i<size)
		{
			r= (int)(Math.random()*list.size());
			r=list.get(r);
			centers[i]=r;
			i++;
			list2.remove(new Integer(r));
			vec=a.getVector(r);
			for (int j=0; j<n; j++)
				if (vec[j]==1)
					list.remove(new Integer(j));
			
		}
		if (i==size)
			return centers;
		
		for ( ;i<size;i++)
		{
			r= (int)(Math.random()*list2.size());
			r=list2.get(r);
			centers[i]=r;
			i++;
			list2.remove(new Integer(r));
		}		
		
		return centers;
	}


	
}
